Users are increasingly performing tasks using remote computing resources, often referred to as part of “the cloud.” This has many advantages, as users do not have to purchase and maintain dedicated hardware and software, and instead can pay for only those resources that are needed at any given time, where those resources typically will be managed by a resource provider. Users can perform tasks such as storing data to various types of resources offered by a resource provider. In many instances, a customer device will establish a connection with a content server, for example, and send requests over that connection. It is possible, however, that an unintended third party can intercept this connection, and can then send and receive requests that appear to come from the intended parties to the connection. In many instances a customer can determine when such a “man in the middle” attack is occurring, due to the difference in expected server certificate or other such information, but it can be difficult for the server side as there generally is no customer certificate to use for verification.